'''
@Problem description:
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
给定n个坐标(i,ai)，其中i从1到n，ai非负，从(i,0)到(i,ai)画n条线段，求两条线段使得这两条线段和x轴组成的容器可以装最多的水。
假定容器不能倾斜，n最小是2

@For example:
'''


class Solution:
    '''
    从两边开始往中间扫，每次选取较长的线段不动。
    为什么总可以找到最优解？
        因为宽在变小，高在变大，可以理解为一个递归的过程。
        每次移动时可以保证没有计算的两条边组成的面积总包含在已经计算过的两条边的面积之中，
        即 alreadyCulArea > noCulArea，因为noCulArea在保证一条边相等的情况下另一条边小于alreadyCulArea
    @复杂度：
    Time complexity : O(n)
    Space complexity : O(1)
    '''
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        s = 0
        l = 0
        r = len(height) - 1
        while (l < r):
            s = max(s, (r - l) * min(height[l], height[r]))
            if (height[l] < height[r]):
                l += 1
            else:
                r -= 1
        return s
